翻訳と辞書 Words near each other ・ Pathari-Sanischare Municipality ・ Path 26 ・ Path 27 ・ Path 46 ・ Path 61 ・ Path 62 ・ Path 64 ・ Path 66 ・ Path analysis ・ Path analysis (computing) ・ Path analysis (statistics) ・ PATH Biobank ・ Path coefficient ・ Path coloring ・ Path computation element ・ Path cover ・ Path dependence ・ Path expression ・ Path Finder ・ Path Finder (Transformers) ・ PATH Foundation ・ Path Grant Deed ・ Path graph ・ Path Head Watermill ・ Path integral ・ Path integral formulation ・ Path integral molecular dynamics ・ Path integral Monte Carlo ・ Path integrals in polymer science ・ Path integration Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Path cover ： ウィキペディア英語版 Path cover Given a directed graph ''G'' = (''V'', ''E''), a path cover is a set of directed paths such that every vertex ''v'' ∈ ''V'' belongs to at least one path. Note that a path cover may include paths of length 0 (a single vertex).〔, Section 2.5.〕 A ''path cover'' may also refer to a vertex-disjoint path cover, i.e., a set of paths such that every vertex ''v'' ∈ ''V'' belongs to ''exactly'' one path.〔.〕 ==Properties== A theorem by Gallai and Milgram shows that the number of paths in a smallest path cover cannot be larger than the number of vertices in the largest independent set.〔, Theorem 2.5.1.〕 In particular, for any graph ''G'', there is a path cover ''P'' and an independent set ''I'' such that ''I'' contains exactly one vertex from each path in ''P''. Dilworth's theorem follows as a corollary of this result. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Path cover」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.